home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / New System Software Extensions / OpenDoc A6 / OpenDoc Parts Framework / OPF / Found / BCCollec / Support / BCUnboun.cpp < prev    next >
Encoding:
Text File  |  1994-04-21  |  8.3 KB  |  302 lines  |  [TEXT/MPS ]
  1. //  The C++ Booch Components (Version 2.1)
  2. //  (C) Copyright 1990-1993 Grady Booch. All Rights Reserved.
  3. //
  4. //  Restricted Rights Legend
  5. //  Use, duplication, or disclosure is subject to restrictions as set forth 
  6. //  in subdivision (c)(1)(ii) of the Rights in Technical Data and Computer 
  7. //  Software clause at DFARS 252.227-7013. 
  8. //
  9. //  BCUnboun.cpp
  10. //
  11. //  This file contains the definition for the list-based class
  12. //  used for the representation of unbounded structures.
  13.  
  14. #include "BCUnboun.h"
  15.  
  16. template<class Item, class StorageManager>
  17. BC_TUnbounded<Item, StorageManager>::BC_TUnbounded()
  18.   : fRep(0),
  19.     fLast(0),
  20.     fSize(0),
  21.     fCache(0),
  22.     fCacheIndex(0) {}
  23.  
  24. template<class Item, class StorageManager>
  25. BC_TUnbounded<Item, StorageManager>::
  26.   BC_TUnbounded(const BC_TUnbounded<Item, StorageManager>& c)
  27.     : fRep(0),
  28.       fLast(0),
  29.       fSize(c.fSize),
  30.       fCache(0),
  31.       fCacheIndex(0)
  32. {
  33.   operator=(c);
  34. }
  35.  
  36. template<class Item, class StorageManager>
  37. BC_TUnbounded<Item, StorageManager>::~BC_TUnbounded()
  38. {
  39.   Clear();
  40. }
  41.  
  42. template<class Item, class StorageManager>
  43. BC_TUnbounded<Item, StorageManager>&
  44.   BC_TUnbounded<Item, StorageManager>::
  45.     operator=(const BC_TUnbounded<Item, StorageManager>& c)
  46. {
  47.   if (this == &c)
  48.     return *this;
  49.   Clear();
  50.   BC_TNode<Item, StorageManager>* ptr = c.fLast;
  51.   if (ptr) {
  52.     fRep = fLast = new BC_TNode<Item, StorageManager>(ptr->fItem, 0, 0);
  53.     ptr = ptr->fPrevious;
  54.     while (ptr) {
  55.       fRep = new BC_TNode<Item, StorageManager>(ptr->fItem, 0, fRep);
  56.       ptr = ptr->fPrevious;
  57.     }
  58.   }
  59.   fSize = c.fSize;
  60.   return *this;
  61. }
  62.  
  63. template<class Item, class StorageManager>
  64. BC_Boolean BC_TUnbounded<Item, StorageManager>::
  65.   operator==(const BC_TUnbounded<Item, StorageManager>& c) const
  66. {
  67.   if (this == &c)
  68.     return 1;
  69.   if (fSize == c.fSize) {
  70.     BC_TNode<Item, StorageManager>* ptr1 = fRep;
  71.     BC_TNode<Item, StorageManager>* ptr2 = c.fRep;
  72.     for (; ptr1; ptr1 = ptr1->fNext, ptr2 = ptr2->fNext)
  73.       if (ptr1->fItem != ptr2->fItem)
  74.         return 0;
  75.     return 1;
  76.   } else
  77.     return 0;
  78. }
  79.  
  80. template<class Item, class StorageManager>
  81. void BC_TUnbounded<Item, StorageManager>::Clear()
  82. {
  83.   while (fRep) {
  84.     BC_TNode<Item, StorageManager>* ptr = fRep;
  85.     fRep = fRep->fNext;
  86.     delete ptr;
  87.   }
  88.   fRep = fLast = fCache = 0;
  89.   fSize = fCacheIndex = 0;
  90. }
  91.  
  92. template<class Item, class StorageManager>
  93. void BC_TUnbounded<Item, StorageManager>::Insert(const Item& item)
  94. {
  95.   fRep = new BC_TNode<Item, StorageManager>(item, 0, fRep);
  96.   if (!fLast)
  97.     fLast = fRep;
  98.   fSize++;
  99.   fCache = fRep;
  100.   fCacheIndex = 0;
  101. }
  102.  
  103. template<class Item, class StorageManager>
  104. void BC_TUnbounded<Item, StorageManager>::Insert(const Item& i, BC_Index before)
  105. {
  106.   BC_Assert((before < fSize), 
  107.             BC_XRangeError((const char*)"BC_TUnbounded::Insert", BC_kInvalidIndex));
  108.   if (!fSize || !before)
  109.     Insert(i);
  110.   else {
  111.     ItemAt(before);
  112.     BC_TNode<Item, StorageManager>* ptr = 
  113.       new BC_TNode<Item, StorageManager>(i, fCache->fPrevious, fCache);
  114.     if (!ptr->fPrevious)
  115.       fRep = ptr;
  116.     fSize++;
  117.     fCache = ptr;
  118.   }
  119. }
  120.  
  121. template<class Item, class StorageManager>
  122. void BC_TUnbounded<Item, StorageManager>::Append(const Item& item)
  123. {
  124.   fLast = new BC_TNode<Item, StorageManager>(item, fLast, 0);
  125.   if (!fRep)
  126.     fRep = fLast;
  127.   fSize++;
  128.   fCache = fLast;
  129.   fCacheIndex = fSize - 1;
  130. }
  131.  
  132. template<class Item, class StorageManager>
  133. void BC_TUnbounded<Item, StorageManager>::
  134.   Append(const Item& i, BC_Index after)
  135. {
  136.   BC_Assert((after < fSize), 
  137.             BC_XRangeError((const char*)"BC_TUnbounded::Append", BC_kInvalidIndex));
  138.   if (!fSize || (after == fSize))
  139.     Append(i);
  140.   else {
  141.     ItemAt(after);
  142.     BC_TNode<Item, StorageManager>* ptr = 
  143.       new BC_TNode<Item, StorageManager>(i, fCache, fCache->fNext);
  144.     if (!ptr->fNext)
  145.       fLast = ptr;
  146.     fSize++;
  147.     fCache = ptr;
  148.     fCacheIndex++;
  149.   }
  150. }
  151.  
  152. template<class Item, class StorageManager>
  153. void BC_TUnbounded<Item, StorageManager>::Remove(BC_Index at)
  154. {
  155.   BC_Assert((at < fSize), 
  156.             BC_XRangeError((const char*)"BC_TUnbounded::Remove", BC_kInvalidIndex));
  157.   BC_Assert(fSize, BC_XUnderflow((const char*)"BC_TUnbounded::Remove", BC_kEmpty));
  158.   if (fSize == 1)
  159.     Clear();
  160.   else {
  161.     ItemAt(at);
  162.     BC_TNode<Item, StorageManager>* ptr = fCache;
  163.     if (!ptr->fPrevious)
  164.       fRep = ptr->fNext;
  165.     else
  166.       ptr->fPrevious->fNext = ptr->fNext;
  167.     if (!ptr->fNext)
  168.       fLast = ptr->fPrevious;
  169.     else
  170.       ptr->fNext->fPrevious = ptr->fPrevious;
  171.     fSize--;
  172.     if (ptr->fNext)
  173.       fCache = ptr->fNext;
  174.     else if (ptr->fPrevious) {
  175.       fCache = ptr->fPrevious;
  176.       fCacheIndex--;
  177.     } else {
  178.       fCache = 0;
  179.       fCacheIndex = 0;
  180.     }
  181.     delete ptr;
  182.   }
  183. }
  184.  
  185. template<class Item, class StorageManager>
  186. void BC_TUnbounded<Item, StorageManager>::Replace(BC_Index at, const Item& item)
  187. {
  188.   BC_Assert((at < Length()),
  189.             BC_XRangeError((const char*)"BC_TDynamic::Replace", BC_kInvalidIndex));
  190.   if (!(fCache && (at == fCacheIndex))) {
  191.     BC_TNode<Item, StorageManager>* ptr = fRep;
  192.     for (BC_Index index = 0; (index < fSize); index++) {
  193.       if (index == at) {
  194.         fCache = ptr;
  195.         fCacheIndex = index;
  196.         break;
  197.       } else
  198.         ptr = ptr->fNext;
  199.     }
  200.   }
  201.   fCache->fItem = item;
  202. }
  203.  
  204. template<class Item, class StorageManager>
  205. BC_Index BC_TUnbounded<Item, StorageManager>::Length() const
  206. {
  207.   return fSize;
  208. }
  209.  
  210. template<class Item, class StorageManager>
  211. const Item& BC_TUnbounded<Item, StorageManager>::ItemAt(BC_Index index) const
  212. {
  213.   if (fCache) {
  214.     if (index == fCacheIndex)
  215.       return fCache->fItem;
  216.   else if (index == fCacheIndex + 1) {
  217.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCache = 
  218.         fCache->fNext;
  219.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCacheIndex++;
  220.       return fCache->fItem;
  221.     } else if (index == fCacheIndex - 1) {
  222.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCache = 
  223.         fCache->fPrevious;
  224.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCacheIndex--;
  225.       return fCache->fItem;
  226.     }
  227.   }
  228.   BC_TNode<Item, StorageManager>* ptr = fRep;
  229.   for (BC_Index listIndex = 0; (listIndex < fSize); listIndex++)
  230.     if (listIndex == index) {
  231.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCache = ptr;
  232.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCacheIndex =
  233.          listIndex;
  234.       return ptr->fItem;
  235.     } else
  236.      ptr = ptr->fNext;
  237.   return ptr->fItem;
  238. }
  239.  
  240. template<class Item, class StorageManager>
  241. Item& BC_TUnbounded<Item, StorageManager>::ItemAt(BC_Index index)
  242. {
  243.   if (fCache) {
  244.     if (index == fCacheIndex)
  245.       return fCache->fItem;
  246.   else if (index == fCacheIndex + 1) {
  247.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCache = 
  248.         fCache->fNext;
  249.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCacheIndex++;
  250.       return fCache->fItem;
  251.     } else if (index == fCacheIndex - 1) {
  252.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCache = 
  253.         fCache->fPrevious;
  254.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCacheIndex--;
  255.       return fCache->fItem;
  256.     }
  257.   }
  258.   BC_TNode<Item, StorageManager>* ptr = fRep;
  259.   for (BC_Index listIndex = 0; (listIndex < fSize); listIndex++)
  260.     if (listIndex == index) {
  261.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCache = ptr;
  262.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCacheIndex =
  263.          listIndex;
  264.       return ptr->fItem;
  265.     } else
  266.      ptr = ptr->fNext;
  267.   return ptr->fItem;
  268. }
  269.  
  270. template<class Item, class StorageManager>
  271. BC_ExtendedIndex BC_TUnbounded<Item, StorageManager>::
  272.   Location(const Item& i, BC_Index start) const
  273. {
  274.   BC_Assert((start <= fSize),
  275.             BC_XRangeError((const char*)"BC_TUnbounded::Location", BC_kInvalidIndex));
  276.   if ((!start) && fCache && (fCache->fItem == i))
  277.     return fCacheIndex;
  278.   BC_TNode<Item, StorageManager>* ptr = fRep;
  279.   for (BC_Index index = 0; (index < start); index++)
  280.     ptr =  ptr->fNext;
  281.   for (; (index < fSize); index++)
  282.     if (ptr->fItem == i) {
  283.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCache = ptr;
  284.       ((BC_TUnbounded<Item, StorageManager>&)(*this)).fCacheIndex = index;
  285.       return index;
  286.     } else
  287.       ptr = ptr->fNext;
  288.   return -1;
  289. }
  290.  
  291. template<class Item, class StorageManager>
  292. void* BC_TUnbounded<Item, StorageManager>::operator new(size_t s)
  293. {
  294.   return StorageManager::Allocate(s);
  295. }
  296.  
  297. template<class Item, class StorageManager>
  298. void BC_TUnbounded<Item, StorageManager>::operator delete(void* p, size_t s)
  299. {
  300.   StorageManager::Deallocate(p, s);
  301. }
  302.